1819F - Willy-nilly Crack Into Release - CodeForces Solution

#include<cstdio>
#include<algorithm>
using namespace std;

#define ll long long int
const ll inf=1ll<<50;
int n,q,cnt=100;
int ch[2000200][4];
int siz[2000200];
int dep[2000200];
int par[2000200];
ll dpM[2000200][4][4];
ll dpm[2000200][4][4];
ll wM1[22],wm1[22];
ll wM2[22],wm2[22];
int son(int p)
{
	int res,w=0;
	for(int i=0;i<4;i++)
		if(ch[p][i]>=100){
			res=ch[p][i]; w++;
		}
	if(w!=1) return -1;
	return res;
}
int check2(void)
{
	int a=100;
	while(son(a)!=-1)
		a=son(a);
	int x=-1,y=-1;
	for(int i=0;i<4;i++)
		if(ch[a][i]>=100){
			if(x==-1) x=i;
			else y=i;
		}
	if((x+y)%2==0) return 0;
	int b=ch[a][y],c=ch[a][x];
	while(son(b)!=-1){
		if(ch[b][x]<100) return 0;
		b=ch[b][x];
	}
	while(son(c)!=-1){
		if(ch[c][y]<100) return 0;
		c=ch[c][y];
	}
	return 1;
}
void updatedp(int s)
{
	while(s>=100){
		int z,w,a,b,t1,t2;
		for(int x=0;x<4;x++)
			for(int y=0;y<4;y++){
				a=ch[s][x]; b=ch[s][y];
				dpM[s][x][y]=-inf;
				dpm[s][x][y]=inf;
				if((x+y)&1){
					if((x+1)%4==y){
						z=(x+3)%4; w=(y+1)%4;
					}
					else{
						w=(y+3)%4; z=(x+1)%4;
					}
					t1=ch[s][z]; t2=ch[s][w];
					dpM[s][x][y]=max(dpM[s][x][y],dpM[a][x][z]+dpM[t1][x][w]+dpM[t2][z][y]+dpM[b][w][y]+3);
					dpm[s][x][y]=min(dpm[s][x][y],dpm[a][x][z]+dpm[t1][x][w]+dpm[t2][z][y]+dpm[b][w][y]+3);
					if(ch[s][z]<100&&ch[s][w]<100){
						dpM[s][x][y]=max(dpM[s][x][y],dpM[a][x][y]+dpM[b][y][x]+1);
						dpm[s][x][y]=min(dpm[s][x][y],dpm[a][x][y]+dpm[b][y][x]+1);
					}
				}
				else{
					z=(x^1); w=(y^1);
					if(ch[s][z]<100){
						t1=ch[s][w];
						dpM[s][x][y]=max(dpM[s][x][y],dpM[a][x][w]+dpM[t1][x][y]+dpM[b][w][y]+2);
						dpm[s][x][y]=min(dpm[s][x][y],dpm[a][x][w]+dpm[t1][x][y]+dpm[b][w][y]+2);
					}
					if(ch[s][w]<100){
						t1=ch[s][z];
						dpM[s][x][y]=max(dpM[s][x][y],dpM[a][x][z]+dpM[t1][x][y]+dpM[b][z][y]+2);
						dpm[s][x][y]=min(dpm[s][x][y],dpm[a][x][z]+dpm[t1][x][y]+dpm[b][z][y]+2);
					}
				}
				if(dpM[s][x][y]<0) dpM[s][x][y]=-inf;
			}
		s=par[s];
	}
	return;
}

int main(void)
{
	scanf("%d%d",&n,&q);
	wm1[0]=wM1[0]=wm2[0]=wM2[0]=0;
	for(int i=1;i<=n;i++){
		wM1[i]=2*wM1[i-1]+2*wM2[i-1]+3;
		wm1[i]=2*wm1[i-1]+1;
		wM2[i]=2*wM1[i-1]+wM2[i-1]+2;
		wm2[i]=2*wm1[i-1]+wm2[i-1]+2;
	}
	for(int i=0;i<=n;i++)
		for(int x=0;x<4;x++)
			for(int y=0;y<4;y++){
				if((x+y)&1){
					dpM[i][x][y]=wM1[i];
					dpm[i][x][y]=wm1[i];
				}
				else{
					dpM[i][x][y]=wM2[i];
					dpm[i][x][y]=wm2[i];
				}
			}
	dep[100]=n;
	for(int a=0;a<4;a++)
		ch[100][a]=dep[100]-1;
	while(q--){
		char str[22];
		scanf(" %s",str);
		int pos=100,ins=0;
		for(int i=0;i<n;i++){
			int x=str[i]-'a';
			if(ch[pos][x]<100){
				++cnt; par[cnt]=pos;
				dep[cnt]=dep[pos]-1;
				for(int a=0;a<4;a++)
					ch[cnt][a]=dep[cnt]-1;
				ch[pos][x]=cnt; ins=1;
			}
			pos=ch[pos][x];
		}
		if(ins==1){
			for(int a=0;a<4;a++)
				for(int b=0;b<4;b++)
					dpM[pos][a][b]=dpm[pos][a][b]=0;
			updatedp(par[pos]);
		}
		else{
			int lst=-1;
			while(pos>100&&siz[pos]==1){
				lst=pos; pos=par[pos];
			}
			for(int a=0;a<4;a++)
				if(ch[pos][a]==lst)
					ch[pos][a]=dep[pos]-1;
			updatedp(pos);
		}
		while(pos>=100){
			if(ins==1) siz[pos]++;
			else siz[pos]--;
			pos=par[pos];
		}
		ll ansM=-inf,ansm=inf;
		for(int p=100;p!=-1;p=son(p))
			if(ch[p][0]>=0){
				ansM=max(ansM,dpM[ch[p][0]][3][1]+dpM[ch[p][1]][0][2]+dpM[ch[p][2]][1][3]+dpM[ch[p][3]][2][0]+4);
				ansm=min(ansm,dpm[ch[p][0]][3][1]+dpm[ch[p][1]][0][2]+dpm[ch[p][2]][1][3]+dpm[ch[p][3]][2][0]+4);
			}
		if(siz[100]<=1||(siz[100]==2&&check2()==1)){
			ansM=max(ansM,2ll);
			ansm=min(ansm,2ll);
		}
		if(ansm==inf) printf("-1\n");
		else printf("%lld %lld\n",ansm,ansM);
	}
	return 0;
}